package demo.ybt;

public class P1258 {

    public static void main(String[] args) {
        P1258 p1258= new P1258();
        int res = p1258.res(new int[][]{{13,0,0,0,0}, {11, 8,0,0,0}, {12, 7, 26,0,0},
                {6, 14, 15, 8,0}, {12, 7, 13, 24, 11}});
        System.out.println(res);
    }

    public int res(int[][] t) {
        /**
         *           [13
         *         [11 8
         *       [12 7  26
         *     [6  14 15 8
         *   [12 7  13 24 11
         *
         *   dp[2][1]= dp[1][0]+t[2][1] | dp[1][1]+t[2][1]
         *   dp[i][j]=Max(dp[i-1][j-1]+t[i][j],dp[i-1][j]+t[i][j])
         */
        //构建一个dp数组，存储当前路径的  和
        //dp[i][j]代表  位置为t[i][j]的路径和

        //高度
        int h = t.length;

        //最后一行的长
        int w = t[t.length-1].length;
        int dp[][] = new int[h][w];

        int max = 0;
        for (int i = 0; i < w; i++) {
            dp[0][i] = t[0][i];
            max = Math.max(dp[0][i], max);
        }
        for (int i = 1; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dp[i][j] = dp[i - 1][j] + t[i][j];
                if (j - 1 >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + t[i][j], dp[i][j]);
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max;
    }
}
